Linked List
- Tricky topics, difficult to implement correctly
- There's a few pattern to memorize and a few fundamental questions that should be reviewed regularly
- Good overview:
- Problems lists:
Pattern
Dummy Head / Sentinel Node
- Saves you from creating special edge condition logic in order to operate on the head of a linked list
- Only involves creating one extra dummy node pointing to the final answer or list that you will return
- This is the most important technique/pattern as it can be used together with other ones
- Used this when there’s a chance the first node is going to be changed for any reason(swapped, removed etc)
If you find yourself writing a solution where you need to introduce a special case to initialize the head of a linked list, and the logic for handling the head is the same as the logic for handling the rest of the linked list, you should consider using a dummy node to simplify your solution.
Using a dummy node under these conditions involves the following 3 steps:
1. Creating the dummy node to represent the head of the linked list you are constructing.
2. Now, you can iteratively append nodes to the end that linked list based on the logic of the problem.
3. Returning dummy.next as the head of the linked list you constructed.
Example: Delete a node in a linked list given the value of the node you want to delete
class Node(object):
def __init__(self, v):
self.val = v
self.next = None
def delete_node(head, val):
d = Node("dummy") # 1
d.next = head
p = d
c = head
while c:
if c.val == val:
p.next = c.next # 2
return d.next # 3
p = c
c = c.next
return d.next # 4
- The creation of the dummy head, in this case it is initialized to point to the original list
- Because we created the dummy head we don't have to treat deleting the head of the original list any different from other elements in the list
- The dummy head points to the answer list so we simply return the next node as the head of the answer
- If we don't happen to find the item setting the dummy head to the original list makes it still point to the correct answer
https://leetcode.com/problems/delete-node-in-a-linked-list
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
dummy = ListNode(0, node)
while node.next:
node.val = node.next.val
dummy = node
node = node.next
dummy.next = None
https://leetcode.com/problems/merge-two-sorted-lists
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
head = dummy
while list1 and list2:
if list1.val <= list2.val:
head.next = list1
list1 = list1.next
else:
head.next = list2
list2 = list2.next
head = head.next
if list1:
head.next = list1
if list2:
head.next = list2
return dummy.next
https://leetcode.com/problems/remove-nth-node-from-end-of-list
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
p1, p2 = ListNode(0, head), ListNode(0, head)
while n > 0:
p1 = p1.next
n -= 1
newHead = p2
while p1 and p1.next:
p1 = p1.next
p2 = p2.next
p2.next = p2.next.next
return newHead.next
Multiple Pass Technique
- Most computation on a list will require O(N) time complexity, so a simple but very technique is to pass through the list some number of times to calculate some summary of the list that will simplify your algorithm.
- One example that we see a lot is the need to calculate the length of the list
Example: Find the intersection of 2 list
- We can iterate through the 2 list, find out the length of the 2 list
- Compare the length of the 2 list, whichever is longer will be strip down so that both list will have the same length
- Now the problem of iterating 2 list at the same time to find the intersection (node with same value) is trivial
Linked List Two Pointer
- Normal two pointer
- [[14 Patterns DSA#3. Fast and Slow pointers | Fast and Slow Pointer]]
Example: Detect cycle in Linked List using Fast and Slow pointer
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head is None or head.next is None:
return False
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
- The intuition here is that if there is a cycle, then the list can be thought of as a circle. Similar to a race track, the fast pointer must eventually cross paths with the slower pointer, whereas if there is not a cycle they will never cross paths.
https://leetcode.com/problems/middle-of-the-linked-list
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow, fast = ListNode(0, head), ListNode(0, head)
while fast and fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
return slow.next
https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow, fast = ListNode(0, head), ListNode(0, head)
dummy = slow
while fast and fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
Reverses a Linked List
- This not really a pattern or technique, but it is a LC problem on its own
- However, there is a lot of Linked List problem can be solved using reverse a list or a portion of the list
- Almost need to memorize thishttps://leetcode.com/problems/reverse-linked-list
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
newNext = None
while head:
nextNode = head.next
head.next = newNext
newNext = head
head = nextNode
return newNext
- This is a good question that encompasses a few patterns https://leetcode.com/problems/palindrome-linked-list
def isPalindrome(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
newNext = None
while slow:
temp = slow.next
slow.next = newNext
newNext = slow
slow = temp
left, right = head, newNext
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
https://leetcode.com/problems/reorder-list
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
slow, fast = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
middle = slow
head2 = None
while middle:
temp = middle.next
middle.next = head2
head2 = middle
middle = temp
switch = False
while head and head2:
if head == head2:
return
if not switch:
temp = head.next
head.next = head2
head = temp
else:
temp = head2.next
head2.next = head
head2 = temp
switch = not switch
Example
1.Middle of the linked List: Given a non empty singly linked list with head node head, return a middle node of linked list Intuition: ^af80bb
- We can use [[Linked List#Linked List Two Pointer | Two Pointer]] moving at different speed, one move twice at fast at the other so when the fast one reach the end, the slow one will be the middle node
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Palindrome Linked: Given a singly linked list, determine if it is a palindrome Intuition:
A palindrome is the same reading forward and backward, or in other word, can be divided into 2 part with the later being the reverse of the former
With the above understanding in mind, we can
- Find the middle node of the linked list ([[#^af80bb | Middle of the linked list]])
- Reverse the second part ([[Linked List#Reverses a Linked List | Reverse a Linked list]])
- Start from the beginning of 2 list, check if they are similar
Reorder List: Given a singly linked list: 0 -> 1 -> 2 -> ... -> n. Reorder it to: 0 -> n -> 2 -> n-1 -> ... (Example: 1-2-3-4 reorder to 1-4-2-3) Intuition:
We can see that it is similar to having two pointer, one going forward and one going backward and connect the two node at the two pointer together. However we can't going backward in a singly linked list. But we can see that if we keep moving backward and forward the pointers will meet at the middle of the list and then stop there.
We can find the [[#^af80bb | middle of the linked list]]
Reverse the second part ([[Linked List#Reverses a Linked List | Reverse a Linked list]])
Starting from the beginning of 2 list, merge them alternatively.